//There are n bulbs that are initially off. You first turn on all the bulbs, 
//then you turn off every second bulb. 
//
// On the third round, you toggle every third bulb (turning on if it's off or 
//turning off if it's on). For the iᵗʰ round, you toggle every i bulb. For the nᵗʰ 
//round, you only toggle the last bulb. 
//
// Return the number of bulbs that are on after n rounds. 
//
// 
// Example 1: 
//
// 
//Input: n = 3
//Output: 1
//Explanation: At first, the three bulbs are [off, off, off].
//After the first round, the three bulbs are [on, on, on].
//After the second round, the three bulbs are [on, off, on].
//After the third round, the three bulbs are [on, off, off]. 
//So you should return 1 because there is only one bulb is on. 
//
// Example 2: 
//
// 
//Input: n = 0
//Output: 0
// 
//
// Example 3: 
//
// 
//Input: n = 1
//Output: 1
// 
//
// 
// Constraints: 
//
// 
// 0 <= n <= 10⁹ 
// 
// Related Topics 脑筋急转弯 数学 👍 293 👎 0

package leetcode.editor.cn;

public class P319BulbSwitcher {
    public static void main(String[] args) {
        Solution solution = new P319BulbSwitcher().new Solution();
        solution.bulbSwitch(3);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int bulbSwitchMe(int n) {
            boolean[] bulb = new boolean[n];
            for (int i = 1; i <= n; i++) {
                for (int j = i - 1; j < n; j += i) {
                    bulb[j] = !bulb[j];
                }
            }
            int count = 0;
            for (int i = 0; i < n; i++) {
                if (bulb[i]) {
                    count++;
                }
            }
            return count;
        }

        public int bulbSwitch(int n) {

            return (int) Math.sqrt(n + 0.5);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}